package com.zrrd.zuo.bag;

/**
 * @author ywb
 * @Description:
 * @date 2023/4/18 23:38
 */
//w[]和v[]代表重量和价值 bag代表能装载的重量 选择最大的价值 0-1背包问题
public class zobag {
    // 所有的货，重量和价值，都在w和v数组里
    // 为了方便，其中没有负数
    // bag背包容量，不能超过这个载重
    // 返回：不超重的情况下，能够得到的最大价值
    public static int maxValue(int[] w, int[] v, int bag) {
        if (w == null || v == null || w.length != v.length || w.length == 0) {
            return 0;
        }
        // 尝试函数！
        return process(w, v, 0,0, bag);
    }

    // index 0~N
    // rest 负~bag
    public static int process(int[] w, int[] v, int index, int alreadyW,int bag) {
        //当前重量超过 没有此种方案
        if (alreadyW > bag) {
            return -1;
        }
        //重量没超
        if (index == w.length) {
            return 0;
        }
        //没要index
        int p1 = process(w, v, index + 1, alreadyW,bag);
        //要了
        int p2 = 0;
        int next = process(w, v, index + 1, alreadyW+w[index],bag);
        if (next != -1) {
            p2 = v[index] + next;
        }
        return Math.max(p1, p2);
    }
    // 所有的货，重量和价值，都在w和v数组里
    // 为了方便，其中没有负数
    // bag背包容量，不能超过这个载重
    // 返回：不超重的情况下，能够得到的最大价值
    public static int maxValue1(int[] w, int[] v, int bag) {
        if (w == null || v == null || w.length != v.length || w.length == 0) {
            return 0;
        }
        // 尝试函数！
        return process(w, v, 0, bag);
    }

    // index 0~N
    // rest 负~bag
    public static int process(int[] w, int[] v, int index, int rest) {
        if (rest < 0) {
            return -1;
        }
        if (index == w.length) {
            return 0;
        }
        //不要
        int p1 = process(w, v, index + 1, rest);
        int p2 = 0;
        //要
        int next = process(w, v, index + 1, rest - w[index]);
        if (next != -1) {
            p2 = v[index] + next;
        }
        return Math.max(p1, p2);
    }

}
